package mo.leetcode_top;

import java.util.*;

public class L218 {

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return res;
        }
        List<int[]> coors = new ArrayList<>();
        for (int i = 0; i < buildings.length; i++) {
            int[] building = buildings[i];
            coors.add(new int[]{building[0], -building[2]});
            coors.add(new int[]{building[1], building[2]});
        }
        coors.sort((c1, c2) -> {
            if (c1[0] != c2[0]) {
                return c1[0] - c2[0];
            } else {
                return c1[1] - c2[1];
            }
        });

        Queue<Integer> max = new PriorityQueue<>((a, b) -> b - a);
        max.add(0);
        int cur = 0;
        int pre = 0;
        for (int i = 0; i < coors.size(); i++) {
            int[] coor = coors.get(i);
            if (coor[1] < 0) {
                max.add(-coor[1]);
            } else {
                max.remove(coor[1]);
            }
            cur = max.peek();
            if (cur != pre) {
                res.add(Arrays.asList(coor[0], cur));
                pre = cur;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        L218 test = new L218();
        System.out.println(test.getSkyline(new int[][]{{0,2,3}, {2, 5, 3}}));
    }

}
